package com.fe.class05;

import java.util.Arrays;

/**
 * @Description 荷兰国旗问题
 * 以给定的数做为划分值，将数组的数划分区域
 * 1. 划分为两个区域，一个是<=num的，一个是>num的
 * 2. 划分为三个区域，一个是<=num的，一个是=num的，一个是>num的
 * @Author sosuke :-)
 * @Date 2021/12/25 21:09
 */
public class Code02_NetherLandsFlag {

    /**
     * 给定一个数组arr，和一个整数num。请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
     * 要求额外空间复杂度O(1)，即只能使用有限几个变量，时间复杂度O(N)
     * 遍历数组，设计一个<=num的窗口windowIndex，满足条件则windowIndex向右扩
     * 1. 如果arr[i] <= num，将arr[i] 和 arr[windowIndex + 1] 交换，windowIndex右移，i继续遍历
     * 2. 如果arr[i] > num，i继续遍历
     */
    public static void netherLandsFlag01(int[] arr, int num) {
        if (null == arr || arr.length == 1) return;
        // 表示<=num的窗口最右侧边缘位置
        int windowIndex = -1;
        int curIndex = 0;
        while (curIndex <= arr.length - 1) {
            if (arr[curIndex] <= num) {
                swap(arr, curIndex, ++windowIndex);
            }
            curIndex++;
        }
    }

    /**
     * 给定一个数组arr，和一个整数num。请把小于num的数放在数组的左边，等于num的数放中间，大于num的数放在数组的右边。
     * 要求额外空间复杂度O(1)，即只能使用有限几个变量，时间复杂度O(N)
     * 遍历数组，设计一个<num的窗口windowL，和一个>num的窗口windowR，两个窗口会相向移动
     * 1. 如果arr[i] < num，arr[i] 和 arr[windowL + 1] 交换，windowL右移，i继续遍历
     * 2. 如果arr[i] == num，i继续遍历
     * 3. 如果arr[i] > num，arr[i] 和 arr[windowR - 1]交换，windowR左移，i不动
     * @param arr
     * @param num
     * @return 返回中间等于num的左右位置
     */
    public static int[] netherLandsFlag02(int[] arr, int num) {
        if (null == arr) {
            throw new RuntimeException("数组为空");
        }
        if (arr.length == 1 && arr[0] == num) {
            return new int[]{0, 0};
        }
        if (arr.length == 1) {
            return new int[]{-1, -1};
        }
        // 表示<=num的窗口最右侧边缘位置
        int windowL = -1;
        int windowR = arr.length;
        int curIndex = 0;
        while (curIndex < windowR) {
            if (arr[curIndex] < num) {
                swap(arr, curIndex++, ++windowL);
            } else if (arr[curIndex] == num) {
                curIndex++;
            } else {
                swap(arr, curIndex, --windowR);
            }
        }
        return new int[]{windowL + 1, windowR - 1};
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int num = 5;
        int[] arr = {8, 5, 9, 5, 0, 3, 6, 7, 1};
        int[] res = netherLandsFlag02(arr, num);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(res));
    }
}
